public class LinkedTest {
    private Node head; // 链表的头节点
    private Node tail; // 链表的尾节点
    private int size;  // 链表的长度

    // 内部节点类
    private static class Node {
        int data;     // 节点存储的数据
        Node prev;    // 指向前一个节点的引用
        Node next;    // 指向下一个节点的引用

        Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    // 头插法
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) { // 如果链表为空
            head = tail = newNode;
        } else {
            newNode.next = head; // 新节点的next指向当前头节点
            head.prev = newNode; // 当前头节点的prev指向新节点
            head = newNode;     // 更新头节点为新节点
        }
        size++; // 链表长度增加
    }

    // 尾插法
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (tail == null) { // 如果链表为空
            head = tail = newNode;
        } else {
            newNode.prev = tail; // 新节点的prev指向当前尾节点
            tail.next = newNode; // 当前尾节点的next指向新节点
            tail = newNode;     // 更新尾节点为新节点
        }
        size++; // 链表长度增加
    }

    // 任意位置插入
    public void addIndex(int index, int data) {
        if (index < 0 || index > size) { // 检查索引是否合法
            throw new IndexOutOfBoundsException("Index is out of bounds");
        }
        if (index == 0) {
            addFirst(data); // 如果索引为0，调用头插法
        } else if (index == size) {
            addLast(data);  // 如果索引为链表长度，调用尾插法
        } else {
            Node newNode = new Node(data);
            Node current = head;
            for (int i = 0; i < index; i++) { // 遍历到索引的节点
                current = current.next;
            }
            newNode.prev = current.prev; // 新节点的prev指向当前节点的prev
            newNode.next = current;     // 新节点的next指向当前节点
            current.prev.next = newNode; // 当前节点的前一个节点的next指向新节点
            current.prev = newNode;      // 当前节点的prev指向新节点
            size++; // 链表长度增加
        }
    }

    // 查找是否包含关键字key
    public boolean contains(int key) {
        Node current = head;
        while (current != null) { // 遍历链表
            if (current.data == key) {
                return true; // 找到关键字
            }
            current = current.next;
        }
        return false; // 未找到关键字
    }

    // 删除第一次出现关键字为key的节点
    public void remove(int key) {
        Node current = head;
        while (current != null) { // 遍历链表
            if (current.data == key) {
                if (current == head) { // 如果要删除的是头节点
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    } else {
                        tail = null; // 如果链表只有一个节点
                    }
                } else if (current == tail) { // 如果要删除的是尾节点
                    tail = tail.prev;
                    tail.next = null;
                } else { // 如果要删除的是中间节点
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
                size--; // 链表长度减少
                return;
            }
            current = current.next;
        }
    }

    // 删除所有值为key的节点
    public void removeAllKey(int key) {
        Node current = head;
        while (current != null) { // 遍历链表
            if (current.data == key) {
                if (current == head) { // 如果要删除的是头节点
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    } else {
                        tail = null; // 如果链表只有一个节点
                    }
                } else if (current == tail) { // 如果要删除的是尾节点
                    tail = tail.prev;
                    tail.next = null;
                } else { // 如果要删除的是中间节点
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
                size--; // 链表长度减少
            }
            current = current.next;
        }
    }

    // 得到单链表的长度
    public int size() {
        return size;
    }

    // 显示链表内容
    public void display() {
        Node current = head;
        while (current != null) { // 遍历链表
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null"); // 链表末尾
    }

    // 清空链表
    public void clear() {
        head = tail = null; // 将头节点和尾节点置为空
        size = 0;           // 链表长度重置为0
    }

}